package com.mamingchao.issue.two;

public class TwoDimensionArray {

    public static void main(String[] args) {
        int[][] arr = {{1,  4,  7, 11, 15},{2,   5,  8, 12, 19},{3,   6,  9, 16, 22},{10, 13, 14, 17, 24},{18, 21, 23, 26, 30}};

        int targetNum = 30;

        boolean exist = isContain(arr, targetNum);
        String msg = exist ? "二维数组中存在目标数字" + targetNum : "二维数组中不存在目标数字" + targetNum;

        System.out.println(msg);

    }

    private static boolean isContain(int[][] twoDimensionArr, int targetNum) {

        // 二位数组的宽度
        int width = twoDimensionArr[0].length;
        // 二位数组 深度
        int depth = twoDimensionArr.length;

        // 先是从右往左 i是横向的索引，j是纵向的索引;
        // i 和 j 是从二位数组的右上角，开始的 坐标 索引
        int i = width -1;
        int j = 0;

        while(i >= 0 && j < depth ) {

            // 如果当前i 和 j定位的值，等于目标值，直接return true，表示找到
            if (twoDimensionArr[j][i] == targetNum) {
                return true;
            }

            // 如果当前i 和 j定位的值，大于目标值，横轴i向左移动, j 保持不变
            if (twoDimensionArr[j][i] > targetNum) {
                i --;
                continue;
            }
            // 如果当前i 和 j定位的值，小于目标值，横轴j向下移动，i保持不变
            if (twoDimensionArr[j][i] < targetNum && j + 1 < depth && twoDimensionArr[j + 1][i] <= targetNum) {
                j ++;
                continue;
            }

            i --;
            j ++;
        }

        return false;
    }

}
